package dynamicProgramming.review11_15.review11_17;

import Atop100.huisu.Class39;

public class Main647 {

    //TODO:2023/11/17  自己的这种想法不太行
        int ans=0;
        public int countSubstrings1(String s) {
            int len=s.length();
            if(len==1){
                return 1;
            }

            backtracking(s,0);
            return ans;
        }

        public  void  backtracking(String s,int start){
            if(start>=s.length()){
                return;
            }
            for(int i=start;i<s.length();i++){
                System.out.println(start+" "+i);

                System.out.println(s.substring(start,i));
//                if(judge(s,start,i)){
//                    ans++;
//                }
                backtracking(s,i+1);
            }
        }

        public  boolean  judge(String s,int start,int end)   {
//            String s=s1.substring(start,end+1);
            int left=start;
            int  right=end;
            while(left<=right){
                if(s.charAt(left)==s.charAt(right)){
                    left++;
                    right--;
                }else{
                    return false;
                }
            }
            return  true;
        }


    public int countSubstrings(String s) {
        int len = s.length();
        char[] chars = s.toCharArray();
        boolean[][] record = new boolean[len][len];
        int ans = 0;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j <= len - 1; j++) {
                if (chars[j] == chars[i]) {
                    if (j - i <= 1) {
                        ans++;
                        record[i][j] = true;
                    } else if (record[i + 1][j - 1]) {
                            ans++;
                            record[i][j] = true;
                        }
                    }
                }

            }
        return  ans;
    }


    public static void main(String[] args) {
        Main647 main647 = new Main647();
        int abc = main647.countSubstrings("abc");
        System.out.println(abc);


    }
}
